1. Field of the Invention
The present invention is directed to signature recognition and authentication and, more particularly, to a signature recognition and authentication scheme employing unsupervised neural networks acting on vectors in high dimensional space.
2. Description of the Prior Art
Various types of transactions require a party""s signature as an indication of acquiescence to that transaction. For example, signatures are necessary for checks, credit cards and numerous types of legal documents. As a signature often is the only necessary indication of acquiescence to a transaction, forgery of signatures is of great concern.
Early anti-forgery schemes required comparison by a person of an original signature kept on file and a newly executed signature on one of the aforementioned documents. Of course, such human intervention is terribly time consuming and often not reliable.
With increasing computing power, electronic signature recognition and authentication systems have been developed. Such systems typically include an input device such as a digitizing pad or tablet to capture and digitally store the signature image and thereafter act on that stored image in various ways to compare the new signature to a previously-stored xe2x80x9cauthenticxe2x80x9d signature.
For example, U.S. Pat. No. 5,745,598 to Shaw et al. discloses a method whereby a discrete cosine transform or orthogonal transform of the stored signature image is executed. A sequence of global parameters is generated and the image is divided into a plurality of strokes according to segmentation parameters based on the properties of the discrete cosine transform or orthogonal transform. A sequence of feature measurements also are generated and, thereafter, the global parameters, segmentation parameters and feature measurements are stored as representative of the signature. Comparisons are made based on the stored representative characteristics. The method disclosed by Shaw et al., however, is intended to be particularly useful for storing a limited amount of data on, for example, a magnetic card such that verification of signatures can be accomplished at autonomous sites, such as automatic teller machines. Because of the reduced amount of data characterizing any signature, there is, by definition, less reliability in verification.
In U.S. Pat. No. 5,559,895 to Lee et al., there is disclosed a writing pad with a graphics digitizer that converts the continuous lines of the signature into digitized dots. The digitized dots are then located with respect to a coordinate system, and horizontal and vertical coordinates are assigned to each dot. The dots are also assigned values with respect to time. The resulting data represent the simultaneous accumulation of both static and dynamic information. These data are used to calculate each feature of a set of features characterizing the signature. The database used to compare the current signature for the signatory (the person making the signature) consists of a mean and a standard deviation for each feature of the set. While such a system is an improvement over known electronic signature authentication/verification systems, this system is focused on the multi-terminal transaction problem and it too lacks, the reliability necessary for superior signature authentication and verification.
U.S. Pat. No. 5,812,698 to Platt et al. discloses a handwriting recognition system that includes a preprocessing apparatus that uses fuzzy functions to describe the points of a stroke. The final identification of each character is performed by a neural network which operate on xe2x80x9csparse data structuresxe2x80x9d to identify the character""s features. The Platt et al. system is directed to overall handwriting recognition, not signature recognition per se, and thus is deficient in the reliability of recognizing and/or authenticating a signature.
Other systems for signature verification has also been devised in the prior art as well. For instance, U.S. Pat. No. 5,442,715 to Gaborski et al. discloses a method and apparatus for cursive script recognition in which a digital signature is processed neural networks in a time series using moving windows and segmentation. U.S. Pat. No. 5,465,308 to Hutcheson et al. discloses a pattern recognition system where a two dimensional pattern is translated via Fourier transform into a power spectrum and the leading elements of this power spectrum are then used as a features vector and analyzed using a four layer neural network. U.S. Pat. No. 5,553,156 to Obata et al. discloses a complex signature recognition apparatus which utilizes stroke oriented preprocessing and a fuzzy neural network to recognize and verify signatures. U.S. Pat. No. 5,680,470 to Moussa et al. discloses a signature verification system and method in which a signature is preprocessed for test features which may be compared against template signatures to verify the presence or absence of the test features using conventional statistical tools. U.S. Pat. No. 5,828,772 to Kashi et al. discloses a method and apparatus for parametric signature verification using global features and stroke direction codes where the signature is decomposed into spatially oriented, time-ordered line segments. U.S. Pat. No. 5,825,906 to Obata et al. discloses a signature recognition system including a preprocessing subsystem which extracts feature vectors, a recognition network which recognizes patterns and a genetic algorithm used to decide which features are worth considering.
Other related technologies include Optical Character Recognition (OCR) systems and hardware for use in verification systems. For instance, U.S. Pat. No. 5,742,702 to Oki discloses a neural network for character recognition and verification which translates characters into a matrix and identifies the characters using a neural network. U.S. Pat. No. 5,774,571 to Marshall discloses a writing instrument with multiple sensors for biometric verification which includes pressure sensitive cells.
However, these prior art systems fail to provide an effective and particularly reliable signature authentication/verification system which may be readily commercially implemented. Furthermore, with the increasing use of the Internet for a myriad of applications and transactions, verifying accurately and reliably a signature on-line is particularly desirable.
In view of the desire to provide an effective and particularly reliable signature authentication/verification system, it is an object of the present invention to provide a signature authentication/verification method and apparatus that preferably employs self organized neural networks.
It is a further object of the present invention to minimize calculation time and computer memory resources preferably by implementing a predefined process portion that implements hierarchical iconic zooming to convert signature raw data. In an alternative embodiment, a xe2x80x9cWhat/Wherexe2x80x9d network preferably replaces the hierarchical iconic zooming process.
It is yet another object of the present invention to implement an unsupervised neural network to analyze the output of the hierarchical iconic zooming stage. It is still another object of the present invention to provide at least one stage of component integration wherein the response of the neural network is analyzed.
It is another object of the present invention to implement an improved Pi neuron in a second stage of component integration whereby an improved response analysis can be performed.
It is still another object of the present invention to implement in a signature authentication system a means for assessing overgeneralization and effectively counteracting the effects thereof.
In accordance with the present invention there is provided a signature verification system that implements a unique combination of concepts to achieve the desired verification and authentication analyses. One concept is recursive zooming, which is a process that takes signature data and converts the same to a set of vectors in high dimensional space. Another concept is execution of a cumulative ortho-normalization process, a new method for calculating correlation ellipsoids or spheres that contain a group of points in high dimensional space. While many other concepts are described and combined to achieve the present invention, the two concepts mentioned immediately above, either alone or in combination with the other inventive features described herein have, to date, never been applied to a signature verification or authentication system.
As discussed previously, the present invention is used to (1) verify and/or authenticate a user""s signature against forgery and/or to (2) biometrically recognize and/or verify a particular person. The method and apparatus (system) of the present invention operates in two phases. In a first, or learning, phase, the system learns to recognize a user""s signature. For this phase, the user provides several repeatable samples of his signature. The system then analyzes the samples, identifies significant characteristics thereof and learns both to recognize the signature itself and to distinguish the way it is written. In a second, or user verification, phase, the system determines if an input signature matches the samples obtained during the first, or learning, phase.
Thus, in accordance with the present invention, it is significantly more difficult to successfully forge a signature since the forger not only must know how a signature looks, but also how the signature is written. Consequently, the system of the present invention also is very useful as a biometric authentication device and method.
Generally, there are five main sub-systems comprising the present invention: input, recursive zooming, unsupervised neural network and components integrator. Each of these is discussed in brief below and is elaborated upon in the Detailed Description.
(A) Input. The input component receives a signature using an input device, e.g. a mouse, pen or tablet, and generates a description of the signature. The description of the signature preferably is a listing of time and corresponding location in x-y coordinates of the input device.
(B) Recursive zooming. The recursive zooming feature serves a plurality of purposes. The first preferably is to convert the signature to a standard form. This is desirable in that several signatures by the same person are almost never identical. For example, the signature may be smaller or larger, stretched or slightly rotated. To be able to recognize any of these xe2x80x9csamexe2x80x9d signatures it is desirable that the system ignore such discrepancies. By converting the signature to a format that does not depend on the signature size or rotation, the system can ignore these factors and therefore can more accurately compare signatures.
Another feature derived from recursive zooming is conversion of the signature to a form that easily can be handled by a downstream neural network. Because unsupervised neural networks (implemented in the present invention) learn to recognize collections of vectors in high dimensional space, the present invention preferably represents the signature in such a collection. That is, the recursive zooming feature of the present invention converts the time/location representation into a collection of vectors in a high dimensional space.
(C) Unsupervised neural network. Unsupervised neural networks are a collection of neurons that can learn to identify clusters of vectors in space, where each neuron identifies a cluster. The network preferably operates in at least two modes. In the learning mode the neurons learn to identify the clusters or a portion thereof, and in the response mode, each neuron responds to vectors that likely belong to the cluster it learned to recognize. In one preferable embodiment, ellipsoid neurons are used for recognizing ellipsoid clusters. In another preferred embodiment, bubble-shaped neurons are implemented for recognizing clusters that are circular.
(D and E) Component integrators, first and second stages. In the learning phase, the component integrators analyze the network response to the sample signature. In the verification stage, the component integrators compare the network response to the signature with the data collected during the learning process. If a xe2x80x9cstrongxe2x80x9d match exists, the signature is deemed authentic. If not, the signature is deemed likely forged.